//
//  3. 无重复字符的最长子串.swift
//  Top600
//
//  Created by rjb on 2021/8/3.
//

import Foundation

class Solution3 {
    // 用Map记录出现重复的下标。这样就可以实现精准的回退。
    func lengthOfLongestSubstring(_ s: String) -> Int {
        let sArray: [Character] = Array(s)
        var dict: [Character: Int] = [:]
        var result = 0
        var begin = 0
        for end in 0..<sArray.count {
            // 回退index
            if let oldIndex = dict[sArray[end]] {
                while begin <= oldIndex {
                    if begin != oldIndex {
                        dict.removeValue(forKey: sArray[begin])
                    }
                    begin += 1
                }
                dict[sArray[begin]] = begin
            }
            // 更新index
            dict[sArray[end]] = end
            
            let length = end - begin + 1
            result = max(result, length)
        }
        return result
    }
    static func test() {
        let solution = Solution3()
//        let str = "abcabcbb"
//        let str = "bbbbb"
//        let str = "pwwkew"
//        let str = " "
        let str = "au"
        let result = solution.lengthOfLongestSubstring(str)
        print(result)
    }
}
